package com.example.question.tree.tree3;

import com.example.question.tree.tree1.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Code03_105 {
    public static void main(String[] args) {
        int[] pre = new int[]{3, 9, 20, 15, 7};
        int[] in = new int[]{9, 3, 15, 20, 7};
        Code03_105 code = new Code03_105();
        System.out.println(code.buildTree(pre, in));
    }

    /**
     * 前序和中序构造二叉树
     *
     * @param preorder
     * @param inorder
     * @return
     */
    private int preOrderIndex = 0;
    private Map<Integer, Integer> idxMap = new HashMap<>();
    private int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            idxMap.put(inorder[i], i);
        }
        return buildTree(0, preorder.length - 1);
    }

    // 大概的框架是这样

    public TreeNode buildTree(int left, int right) {
        if (right < left) {
            return null;
        }
        int nodeVal = preorder[preOrderIndex];
        TreeNode treeNode = new TreeNode(nodeVal);
        preOrderIndex++;
        int mid = idxMap.get(nodeVal);
        treeNode.left = buildTree(left, mid - 1);
        treeNode.right = buildTree(mid + 1, right);
        return treeNode;
    }
}
